package com.tgy.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

/**
 * @Author: tgy
 * @Date: 2021/2/21 下午10:31
 */
public class _1438_绝对差不超过限制的最长连续子数组_deque {

    public static int longestSubarray(int[] nums, int limit) {
        int left = 0, right = 0;
        int maxLen = 0;

        /**
         * 递增队列，最低数据是最小值
         */
        Deque<Integer> incrementDeque = new LinkedList<>();
        /**
         * 递减队列，最低处是最大值
         */
        Deque<Integer> decrementDeque = new LinkedList<>();


        while (right < nums.length) {

            while (!incrementDeque.isEmpty() && incrementDeque.peekLast() > nums[right]) {

                incrementDeque.removeLast();
            }

            while (!decrementDeque.isEmpty() && decrementDeque.peekLast() < nums[right]) {

                decrementDeque.removeLast();
            }

            incrementDeque.addLast(nums[right]);
            decrementDeque.addLast(nums[right]);

            while (decrementDeque.peekFirst() - incrementDeque.peekFirst() > limit) {

                if (decrementDeque.peekFirst() == nums[left]) {

                    decrementDeque.removeFirst();
                }

                if (incrementDeque.peekFirst() == nums[left]) {

                    incrementDeque.removeFirst();
                }

                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        }

        return maxLen;
    }



    public static void main(String[] args) {

        int[] nums = {10,1,2,4,7,2};
        int k = 5;
        int result = longestSubarray(nums, k);
        System.out.println(result);

    }
}
